#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int SimapleArray[]={6,0,2,0,1,3,4,6,1,3,2};
class PrintInt
	{
	public:
		void operator()(int elem) const
		{
			cout << elem<<' ';
		}
	};

void couting_sort(vector<int> &vecA,vector<int> &vecB,int k)
{
	vector<int> vecC;
	for(int i=0;i<k+1;++i)
		vecC.push_back(0);
	for(int j=0;j<vecA.size();++j)
		++vecC[vecA[j]];
	for(int i=1;i<k+1;++i)
		vecC[i]=vecC[i]+vecC[i-1];
	for(int j=vecA.size()-1;j>=0;--j)
	{
		vecB[vecC[vecA[j]]-1]=vecA[j];
		--vecC[vecA[j]];
	}
}

int main()
{
	vector<int> A;
	
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
	vector<int> B(A);
	cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	cout << "Counting sorts the array"<<endl;
	couting_sort(A,B,6);
	cout << "Array after sorting\n";
	for_each(B.begin(), B.end(), PrintInt());
	cout<<endl;
	return 0;
}